#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int MAXN = 2e7+7;
LL euler[MAXN];
int prime[MAXN], p_cnt;
bool not_p[MAXN];
LL euSum[MAXN];
void Init() {
	p_cnt = 0;
	euler[1] = 0;
	for (int i=2; i<MAXN; ++i) {
		if (!not_p[i]) {
			prime[p_cnt++] = i;
			euler[i] = (i-1);
		}
		for (int j=0; j<p_cnt&&prime[j]*i<MAXN; ++j) {
			not_p[i*prime[j]] = true;
			if (i%prime[j]==0) {
				euler[i*prime[j]] = euler[i] * prime[j];
				break;
			}
			else {
				euler[i*prime[j]] = euler[i] * (prime[j] - 1);
			}
		}
	}
	euSum[0] = 0;
	for (int i=1; i<MAXN; ++i) {
		if (i&1) euSum[i] = (euSum[i-1] + euler[i]/2);
		else euSum[i] = euSum[i-1] + euler[i];
	}
}

int main() {
	#ifdef hai
	freopen("in.txt", "r", stdin);
	#endif
	Init();
	int T;
	cin>>T;
	int n;
	while (T--) {
		scanf("%d", &n);
		int res=0;
		printf("%lld\n", euSum[n]);
	}
	
	return 0;
}
